from 翻译包 import *
import random
from mytools import *

class DetUniq:
	def __init__(self, 深度, 宽度):
		self.深度 = 深度
		self.宽度 = 宽度

		self.过滤器 = []
		for 计数 in 范围(宽度):
			self.过滤器.append([0, 0, 0, 0])

		self.哈希表 = []
		for 计数 in 范围(宽度*(深度 - 1)):
			self.哈希表.append(0)

		self.随机因子 = []
		random.seed(0)
		for 计数 in 范围(深度):
			self.随机因子.append(random.randint(0, 0xffffffff))

	def 更新(self, 数据包):
		标识符 = 数据包
		指纹 = hash1(标识符.encode("utf-8"))&0xffff
		索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[-1])%self.宽度

		if 指纹 == self.过滤器[索引][0]:
			self.过滤器[索引][1] += 1
			self.过滤器[索引][2] += 1
		elif 0 == self.过滤器[索引][1]:
			self.过滤器[索引][0] = 指纹
			self.过滤器[索引][1] += 1
			self.过滤器[索引][2] += 1
		else:
			self.过滤器[索引][1] -= 1
		if self.过滤器[索引][2] > self.过滤器[索引][3]:
			self.过滤器[索引][3] = self.过滤器[索引][2]
		最小上界 = self.过滤器[索引][3]

		for 序号 in 范围(self.深度 - 1):
			索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[序号])%self.宽度+序号*self.宽度
			if self.哈希表[索引] < 最小上界:
				self.哈希表[索引] += 1
				最小上界 = self.哈希表[索引]
		return 最小上界

	def 查询(self, 数据包):
		标识符 = 数据包
		指纹 = hash1(标识符.encode("utf-8"))&0xffff
		索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[-1])%self.宽度
		最小上界 = self.过滤器[索引][3]
		for 序号 in 范围(self.深度 - 1):
			索引 = (hash1(标识符.encode("utf-8"))^self.随机因子[序号])%self.宽度+序号*self.宽度
			if self.哈希表[索引] < 最小上界:
				最小上界 = self.哈希表[索引]
		return 最小上界
	
	def 计算平均计数值(self):
		总计数值 = 0
		for 子项 in self.过滤器:
			总计数值 += 子项[2]
		for 子项 in self.哈希表:
			总计数值 += 子项
		return 总计数值/浮点数(self.深度*self.宽度)

	def 总结(self):
		计数值 = 0
		for 子项 in self.过滤器:
			计数值 += 子项[2]
		输出("计数值:%d" % 计数值)
#		for 序号 in 范围(self.深度 - 1):
#			计数值 = 0
#			for 
